package demo.hw;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/*
题目描述
给定一个整数数组 nums，代表采样点的流量值，找到满足以下条件的三元组 (i, j, k)：

i < j < k
nums[j] > nums[i] 且 nums[j] > nums[k]（即 j 是峰顶）
返回所有满足条件的三元组中 (k - i) 的最小值。若不存在，返回 -1。
输入输出示例
‌示例1‌：
输入：3 5 4 7 2 1
输出：2
说明：满足条件的三元组为 [0, 1, 2]（j=1 是峰顶，k-i=2）。
‌示例2‌：
输入：4 3 2 1
输出：-1
说明：无法找到满足条件的三元组。用java单调栈实现
 */
public class _流量波峰 {
    public static void main(String[] args) {
        int arr[] = {3, 5, 4, 7, 2, 1};
        int m = arr.length;

        int[] left = new int[m];// 向左边查找找出比当前元素小的最近的一个元素位置
        int[] right = new int[m]; // 向右边查找找出比当前元素大的最近的一个元素位置
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);

        Deque<Integer> stack = new ArrayDeque<>();
        // 单调递增栈找左边最近更小的
        for (int i = 0; i < m; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();//弹出栈里面所有大于等于当前元素的 极端场景arr[i]=2，2左边没有比2小的，栈里面要全部弹出
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        // 3 5 4 7 2 1
        // 0 1 2 3 4 5
        // 向左找比i小的索引
        // -1 0 0 2 -1 -1
        System.out.println(Arrays.toString(left));
        stack.clear();
        // 单调递增栈找右边最近更小的
        for (int i = m - 1; i >= 0; i--) { // 3, 5, 4, 7, 2, 1
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();//弹出所有大于等于当前元素的 当num[i]=4时栈里的arr[stack.peek()]=7要弹出，保留2
            }
            if (!stack.isEmpty()) {
                right[i] = stack.peek();
            }
            stack.push(i);
        }
        // i向右找比i小的
        // 4 2 4 4 5 -1
        System.out.println(Arrays.toString(right));
        // 遍历j找最小跨度
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            if (left[i] != -1 && right[i] != -1) {
                int span = right[i] - left[i];
                if (span < min) {
                    min = span;
                }
            }
        }
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
}
